package leetcode.code1224;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	int MAX = (int) 1e5 + 1;

	public int maxEqualFreq(int[] nums) {
		int[] cnts = new int[MAX];// 某一个数的词频
		int[] show = new int[MAX];// 这个词频包含的数字数
		int l = 0, r = nums[nums.length - 1];
		int ans = 0;
		Set<Integer> set = new HashSet<>();
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			boolean ok = false;
			cnts = new int[MAX];// 某一个数的词频
			show = new int[MAX];// 这个词频包含的数字数
			set = new HashSet<>();
			for (int i = 0; i <= mid; i++) {
				int num = nums[i];
				if (cnts[num] != 0) {
					show[cnts[num]] -= 1;
					if (show[cnts[num]] == 0) {
						set.remove(cnts[num]);
					}
				}
				cnts[num]++;
				if (show[cnts[num]] == 0) {
					set.add(cnts[num]);
				}
				show[cnts[num]]++;
			}
			if (set.size() == 1) {
				Integer[] t = set.toArray(new Integer[1]);
				// 全部数字出现次数是1次的情况 || 出现的全是同一种数字
				if (t[0] == 1 || show[t[0]] == 1)
					ok = true;
			} else if (set.size() == 2) {
				Integer[] t = set.toArray(new Integer[2]);
				int max = Math.max(t[0], t[1]);
				int min = Math.min(t[0], t[1]);
				// 两种出现时，出现次数较多出现1次，两者频次差1次，此时大的减1就行
				// 或者 较小的出现1次，去掉这个数字就行
				if ((show[max] == 1 && Math.abs(t[0] - t[1]) == 1) || (min == 1 && show[min] == 1)) {
					ok = true;
				}
			}
			if (ok) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return ans + 1;
	}

	@Override
	public void debug4() {
		H.compare(2, this.maxEqualFreq(H.str2array3("[1,1]")));
		H.compare(25, this.maxEqualFreq(H.str2array3(
				"[1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5,1,1,1,2,2,2,3,3,3,4,4,4,5]")));
		H.compare(13, this.maxEqualFreq(H.str2array3("[2,2,1,1,5,3,3,5,2,1,1,5,3,3,2]")));
		H.compare(5, this.maxEqualFreq(H.str2array3("[1,2,7,3,3,3,4,4,4,4]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
